This invention relates to compression coding of video signals, and more particularly to removing the temporal redundancy that exists in video signals by considering the frame-to-frame displacement of moving objects in the coding process.
The main objective in the bandwidth compression of video signals is to remove the vast amount of redundancy which normally exits in the spatial domain (within a frame) as well as in the temporal direction (frame-to-frame). Attempts to minimize the temporal redundancies can be accomplished by interframe coding techniques. In addition, the temporal redundancies can be exploited more efficiently by taking into consideration the displacements of moving objects in the coding process. Thus, in any motion compensated coding scheme, the coding performance depends heavily on the accuracy of the motion estimation.
There are two distint approaches to motion estimation, pel recursive and block-matching (see, e.g., H. M. Musmann, P. Pirsch, and H. J. Gravoert, "Advances in Picture Coding," Proc. IEEE, Vol. 73, pp. 523-548, April, 1985). In the former method, motion displacement vectors are recursively estimated to minimize the motion compensated prediction error at each pel instant. In the latter approach, the motion estimation is carried out on a block-by-block basis and due to its lesser hardware complexity, is presently considered the most popular method in digital video applications (see, e.g., R. Plomjen et al., "Motion Video Coding in CCIT SGXV--The Video Source Coding," Proc. IEEE, GLOBECOM'88, pp. 997-1004, November, 1988). The main obstacle which has prevented widespread application of motion compensation in real-time video coding, however, is the high computation cost. The evolving ISDN and the growing need for low rate transmission of improved quality video signals at the given ISDN rate (basic rate of 64 kb/s), has promoted the utilization of motion compensated coding. This is in anticipation of the advances in VLSI technology which will facilitate cost effective hardware realization of some of the lesser complex motion estimation algorithms. Progress in VLSI chip implementation of some of these algorithms is reported in the technical literature (see, e.g., T. Komarek and P. Pirsch, "Array Architectures for Blockmatching," pp. 1301-1308; K.-M. Yang, M.-T. Sun, and L. Wu, "A Family of Designs for Motion Compensation Block-Matching Algorithm", pp. 1317-1325; L. Devos and M. Stegherr, "Parameterizable VLSI Architectures for the Full-Search Blockmatching Algorithms," pp. 1309-1316; C.-H. Chou and Y.-C. Chen, "A VLSI Architecture for Real-Time and Flexible Image Template Matching," pp. 1336-1342; and R. C. Kim and S. U. Lee, "A VLSI Architecture for Pel Recursive Motion Estimation Algorithm," pp. 1291-1300, all from IEEE Trans. on Circuits and Systems, special issue on VLSI Implementation for Digital Image and Video Applications, Vol, 36, October, 1989).
Various methods of block-matching estimation have been proposed. For example, block-matching motion estimation with a means absolute difference criterion (see, e.g. T. Koga, I, Iinuma, A. Hirano, Y. Iiyima, and T. Ishiguro, "Motion-Compensated Interframe Coding for Video Conferencing," Proc. of the NTC 81, pp. G5.3.1-G5.3.5, New Orleans, La., December 1981) is a candidate for low bit rate video application due mainly to its relative ease of hardware implementation. Its performance, however, may be less than satisfactory for fast moving video sequences or in the presence of noise. More efficient criteria such as cross-correlation and mean squared difference (see, e.g., S. Kappagantula and K. R. Rao, "Motion Compensated Predictive Coding," SPIE, 27th Proc. 432, pp. G4-70, 1983) are too complex and their hardware requirement is too difficult for practical realization.
An objective of the present invention is to realize maximize performance by a block-matching motion estimation procedure that requires minimum of hardware complexity.